package interview.sort;

import com.study.interfaces.IArraySort;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.SwapUtil.swap;

/**
 * 6. 快速排序
 * <p>
 * 从数列中挑出一个元素，称为 “基准”（pivot）;
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在
 * 基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的
 * 中间位置。这个称为分区（partition）操作；
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 *
 * @author wangxiaozhe
 */
@Slf4j
@SuppressWarnings("all")
public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] arr) {
        // 190401 first
        // 190402 second
        // 190417 third 忘了，看了答案捡起来
        // 190421 fourth 思路基本对，但是答案差点事儿，还是忘了
        // 190427
        // 190428
        // 190504 没看答案两遍过
        // 190509 fifth 看了答案才做出来，但是错的很不值得，之前错过的地方又做错了
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    public static void quickSort(int[] arr, int left, int right) {
        // TODO
    }

    @Test
    public void test() {
        int[] a = {12, 20, 5, 16, 15, 1, 30, 45, 23, 9};
//        int[] a = {2,2,2,2};
        //快速排序
        log.info("result:{}", sort(a));
    }
}












































/*
 public static void quickSort(int[] arr, int left, int right) {
    if (left>right)
        return;

    int i = left;
    int j = right;
    int base = arr[left];

    // 当 i 和 j 不相遇的时候，在循环中进行检索
    while (i != j) {
        // 先由 j 从右往左检索比基准数小的就停下
        // 如果 >= 基准数，就继续走
        while (arr[j] >= base && i < j) {
            j--;
        }

        // 然后由 i 从左向右检索比基准数大的就停下
        // 如果 <= 基准数，就继续走
        while (arr[i] <= base && i < j) {
            i++;
        }

        //i,j指针都停下了，交换i, j元素
        swap(arr, i, j);
    }

    // 如果while循环条件不成立，跳出循环往下执行
    // 条件不成立说明 arr[i], arr[j] 相遇了
    // 就交换基准数 left 和 相遇位置的元素
    arr[left] = arr[i];
    arr[i] = base;

    // 此时左边的都比base小,右边的都比base大
    // 因为i已经是基准数了，不能动了
    quickSort(arr, left,i-1);
    quickSort(arr,i + 1, right);
}
*/
